/**
 * @author ghp
 * @title 两数相加
 */


/**
 * Definition for singly-linked list
 */
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        ListNode i = l1; // 用于遍历l1
        ListNode j = l2; // 用于遍历l2
        ListNode head = new ListNode(); // 构建的新链表的头结点
        ListNode k = head; // 遍历新链表，辅助构建新链表
        int t = 0; // 存储进位 和 求和结果
        // 同时遍历 l1 和 l2
        while (i != null && j != null) {
            t += i.val + j.val;
            k.next = new ListNode(t % 10, null);
            t /= 10;
            k = k.next;
            i = i.next;
            j = j.next;
        }
        // l1还有元素
        while (i != null) {
            t += i.val;
            k.next = new ListNode(t % 10, null);
            t /= 10;
            i = i.next;
            k = k.next;
        }
        // l2还有元素
        while (j != null) {
            t += j.val;
            k.next = new ListNode(t % 10, null);
            t /= 10;
            j = j.next;
            k = k.next;
        }

        // 单独处理进位
        if (t != 0) {
            k.next = new ListNode(t, null);
        }

        return head.next;
    }
}
